package com.zhupf.doublePoint;

import java.util.Deque;
import java.util.LinkedList;
import java.util.concurrent.DelayQueue;

/**
 * @author zhupf
 * @date 2023年10月26日 15:40
 * @Description 42. 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
 * <p>
 * height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * <p>
 * 6
 */
public class Trap {

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap3(height));
    }

    /**
     * 动态规划
     *
     * @param height
     * @return
     */
    public static int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        left[0] = height[0];
        int[] right = new int[n];
        right[n - 1] = height[n - 1];
        for (int i = 1; i < n - 1; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }
        int sum = 0;
        for (int i = 1; i < n - 1; i++) {
            int min = Math.min(right[i], left[i]);
            if (height[i] < min) {
                sum += (min - height[i]);
            }
        }
        return sum;
    }

    /**
     * 单调栈
     *
     * @param height
     * @return
     */
    public static int trap3(int[] height) {
        int ans = 0;
        Deque<Integer> deque = new LinkedList();
        deque.push(0);
        for (int i = 1; i < height.length; i++) {
            while (height[i] > height[deque.peek()]) {
                Integer pop = deque.pop();
                if (deque.isEmpty()) {
                    break;
                }
                Integer peek = deque.peek();
                ans += ((Math.min(height[peek], height[i]) - height[pop]) * (i - peek - 1));
            }
            deque.push(i);
        }
        return ans;
    }

    /**
     * 双指针
     *
     * @param height
     * @return
     */
    public static int trap2(int[] height) {
        int ans = 0;
        int leftmax = 0;
        int rightmax = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] < leftmax) {
                    ans += leftmax - height[left];
                } else {
                    leftmax = height[left];
                }
                left++;
            } else {
                if (height[right] < rightmax) {
                    ans += rightmax - height[right];
                } else {
                    rightmax = height[right];
                }
                right--;
            }
        }
        return ans;
    }

}
